iT邦幫忙

2021 iThome 鐵人賽

DAY 28
1

桶排序法(Bucket Sort),與前面幾篇的排序法不一樣,前面都是經由兩兩互相比較而成的排序,稱為比較排序法,而桶排序是非比較排序,屬於「分配性」的排序。原理是先準備幾個桶子,每個桶子都是有限的固定區間,再將待排序的資料分配到對應區間的桶子中,接著每個桶再個別排序(可以使用別的排序演算法),最後再依序收集排序好的資料。
如果記憶體更大的話, 可以使用增加桶子的數量來降低區間,這樣將可以減少排序的次數,所以桶排序是一種可以用空間來換時間的排序法

操作流程:

  1. 設定定量的空桶子
  2. 走訪原始資料並分配到對應桶子中
  3. 對每個不是空的桶子進行排序
  4. 依序從不是空的桶子中,把排序好資料收集回來

下面利用9 15 12 23 33 26 7 31 42 36由小到大排序
https://ithelp.ithome.com.tw/upload/images/20211009/20121027VehVrEwsQd.jpg


k = 桶子的數量
n = 資料數量
平均時間複雜度為: O(n+k)


JavaScript

function bucketSort(arr){
  let min = Math.min(...arr);
  let max = Math.max(...arr);
  let size = 5
  
  //產生空桶子
  let buckets = Array.from(
    { length: Math.floor((max - min) / size) + 1 },() => []);

	//依規則分類到各桶子
  arr.forEach(function(val){
   	buckets[Math.floor((val - min) / size)].push(val);
  });
     
  result=[];
  //各桶子裡資料排序
  for (i = 0; i < buckets.length; i++) { 
  	buckets[i].sort()//偷懶使用sort(),可以自行使用其他排序法
    //拉出合併
    for (var j = 0; j < buckets[i].length; j++) { 
      result.push(buckets[i][j]); 
    } 
  } 
	
  return result

};

let arr = [9, 15, 12, 23, 33, 26, 7, 31, 42, 36]

console.log(bucketSort(arr))
//[7, 9, 12, 15, 23, 26, 31, 33, 36, 42]

Python

#Bucket Sort
import math
 
def bucketSort(array):
    maxx = max(array)
    minn = min(array)
    size = 5
 
    buckets = [[] for i in range(math.floor((maxx-minn)/size+1))]

    for i in range(len(array)):
        val = int(array[i])
        buckets[math.floor((val-minn)/size)].append(val)
 
    result = []

    for i in range(len(buckets)):
        buckets[i] = sorted(buckets[i])

        for j in range(len(buckets[i])):
            result.append(buckets[i][j])
                
    return result
 
data = [9, 15, 12, 23, 33, 26, 7, 31, 42, 36]

print(bucketSort(data))
#[7, 9, 12, 15, 23, 26, 31, 33, 36, 42]

上一篇
【Day27】[演算法]-堆積排序法 Heap Sort
下一篇
【Day29】[演算法]-基數排序法Radix Sort
系列文
資料結構與演算法,使用JavaScript與Python35
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言